package 中等.贪心思想;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
 * 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
 * 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
 * 请你返回纸上能写出的字典序最小的字符串。
 *
 * @ https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/?envType=daily-question&envId=2025-06-06
 * @date 2025/06/06
 */
public class 使用机器人打印字典序最小的字符串_2434 {

    public static void main(String[] args) {

        使用机器人打印字典序最小的字符串_2434 impl = new 使用机器人打印字典序最小的字符串_2434();

        System.out.println(impl.robotWithString("bac"));

    }

    /**
     * 贪心+栈
     * 如果当前机器人栈顶字符为空，或者大于 ，s剩下字符的最小字符，最小字符前面的字符入栈
     * 如果相等，先将栈顶元素出栈，在将字符串最小字符入栈
     * 如果小于，将栈顶元素出栈
     */
    public String robotWithString(String s) {
        StringBuilder builder = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();

        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }

        int idx = 0;
        while (idx < s.length()) {
            char minChar = findMinChar(cnt);
            if (stack.isEmpty() || stack.peek() > minChar) {

                while (s.charAt(idx) != minChar) {
                    stack.addFirst(s.charAt(idx));
                    cnt[s.charAt(idx) - 'a']--;
                    idx++;
                }
                builder.append(minChar);
                cnt[minChar - 'a']--;
                idx++;
            } else if (stack.peek() <= minChar) {
                Character headChar = stack.pollFirst();
                builder.append(headChar);
            }
        }
        while (!stack.isEmpty()) {
            builder.append(stack.pollFirst());
        }

        return builder.toString();
    }

    private char findMinChar(int[] cnt) {
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > 0) {
                return (char) (i + 'a');
            }
        }
        return 0;
    }

}
